package cn.xkai.exercise.a;

/**
 * @description: 只出现一次的数字
 * 自己的思路：借鉴上一题的手写hash，加入链表，判断链表的next==null时则找到目标值
 * 借鉴的思路：位运算-异或
 * 心得：
 * @author: kaixiang
 * @date: 2022-07-01
 **/
public class Solution26 {
    public int singleNumber(int[] nums) {
        int len = nums.length;
        if (len == 1) {
            return nums[0];
        }
        Node[] hash = new Node[len];
        int zoreCount = 0;
        for (int num : nums) {
            if (num == 0) {
                zoreCount++;
                continue;
            }
            int k = num % len;
            if (k < 0) {
                k += len;
            }
            while (true) {
                if (hash[k] == null) {
                    hash[k] = new Node(num);
                    break;
                } else if (hash[k].value == num) {
                    hash[k].next = hash[k];
                    break;
                } else {
                    // hash冲突简单处理，向后存储，超过边界从头存储
                    k++;
                    if (k >= len) {
                        k -= len;
                    }
                }
            }
        }
        if (zoreCount == 1) {
            return 0;
        }
        for (Node node : hash) {
            if (node != null && node.next == null) {
                return node.value;
            }
        }
        return 0;
    }

    public static class Node {
        int value;
        Node next;

        Node(int value) {
            this.value = value;
        }
    }

    public int singleNumberRefer(int[] nums) {
        int reduce = 0;
        for (int num : nums) {
            reduce = reduce ^ num;
        }
        return reduce;
    }

    public static void main(String[] args) {
        int[] nums = {1, 2, 1, 2, 3};
        Solution26 solution26 = new Solution26();
        System.out.println(solution26.singleNumber(nums));
    }
}
